import java.util.Arrays;

public class Solution691 {
    public int minStickers(String[] stickers, String target) {
        int[] f=new int[1<<target.length()];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0]=0;
        for (String sticker : stickers) {
            int[] g=new int[26];
            for (char c : sticker.toCharArray()) {
                g[c-'a']++;
            }
            for (int i=0;i<(1<<target.length());i++){
                if (f[i]!=Integer.MAX_VALUE){
                    int cal=cal(Arrays.copyOf(g,26),target,i);
                    f[cal]=Math.min(f[cal],f[i]+1);
                }
            }
        }
        return f[(1<<target.length())-1]==Integer.MAX_VALUE?-1:f[(1<<target.length())-1];
    }

    private int cal(int[] f, String target, int state) {
        int ans=state;
        for (int i=0;i<target.length();i++){
            if ((state&(1<<i))==0 && f[target.charAt(i)-'a']>0){
                f[target.charAt(i)-'a']--;
                ans|=(1<<i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution691().minStickers(new String[]{"with","example","science"},"thehat"));
    }
}
